package DP;

/**
 * @author 曹见朋
 * @create 2024-06-13-23:08
 */
public class Main188 {
    // TODO 188. 买卖股票的最佳时机 IV
    public static int maxProfit(int k, int[] prices) {
        int n = prices.length;

        int[][] dp = new int[n][2 * k + 1];
        for(int i = 0; i < 2 * k + 1; i++){
            if(i % 2 == 0){
                dp[0][i] = 0;
            }else{
                dp[0][i] = -prices[0];
            }
        }

        for(int i = 1; i < n; i++){
            for(int j = 0; j < 2 * k + 1; j++){
                if(j == 0){
                    dp[i][j] = dp[i - 1][j];
                }else if(j % 2 == 1){
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
                }
            }
        }

        return dp[n - 1][2 * k];
    }

    public static void main(String[] args) {
        int[] prices = new int[]{3,2,6,5,0,3};
        int i = maxProfit(2, prices);
        System.out.println(i);
    }
}
